package dynamic;

import java.util.Arrays;

/**
 * 题目：求没有重复字符的最长子串(动态规划)
 * y: abcba  返回3
 * ddd    返回1
 *
 * @Author Gavin
 * @date 2021.12.27 21:52
 */
public class solution_2 {
    //第一种方法:暴力破解法，时间复杂度O(n^3)

    /**
     * 第二种方法,滑动窗口思想
     * 思路：
     * 使用两个指针指向头部字符，然后其中一个向后移动，把每个字符记录到hash表里面，
     * 如果遇到某个字符已经存在与hash表中，就减去hash表中对应的这个值的值，然后移动另一个
     * 指针到下一个字符
     */
    //Time:O(n) Space:O(m)
    public static int solution_1(String s) {
        int[] counts = new int[256];//这里使用一个数组替代hash表
        int i = 0, j = 0, maxLen = 0;
        for (; i < s.length(); ++i) {
            //注意这里并不是双重for循环的时间复杂度
            //这里只有O(n)的复杂度，相当于就是把每个字符设置到数组里面了用了O(n)，
            // 然后从数组取值用了O(1)
            for (; j < s.length(); ++j) {
                if (counts[s.charAt(j)] != 0) break;
                counts[s.charAt(j)] += 1;
            }
            maxLen = Math.max(maxLen, j - i);
            counts[s.charAt(i)] -= 1;
        }
        return maxLen;
    }

    /**
     * 第二种方法：比第一种效率高一些
     * 优化点就是i直接跳到重复字符的下一个位置开始重新计算长度，所以这就需要我们把每个
     * 字符所在的位置给记录下来。该方法和上面方法的主要区别就是该方法里面数组存储的是字符
     * 所在的下标位置。
     */
    public static int solution_2(String s) {
        int[] index = new int[256];
        Arrays.fill(index, -1);
        int maxLen = 0;
        for (int i = 0, j = 0; j < s.length(); ++j) {
            //定位i的位置，如果字符不重复那么i的位置就一直为0，如果遇到重复的了
            //就跳到重复位置的下一个位置（这个位置就是下面设置的）
            //这样的目的就是为了处理上面那种方法处理：
            // abcdc这样的情况（第一种方法在处理第二个c的时候还是会从bcdc开始处理
            // ，本方法就是直接处理第二个c位置了）
            i = Math.max(index[s.charAt(j)] + 1, i);
            maxLen = Math.max(maxLen, j - i + 1);
            //把字符和字符对应的下标位置存起来，用于i进行跳转
            index[s.charAt(j)] = j;
        }
        return maxLen;
    }

    //上面的方式不好理解，可以看这个方法理解。
    public static int solution_3(String s) {
        int[] index = new int[256];
        int maxLen = 0;
        for (int i = 0, j = 0; j < s.length(); ++j) {
            //取重复字符下标的后一位
            //i保存的的是重复字符下标大的位置，比如
            //abcdcb 当遇到c重复时候，i的下标值保存为2，然后遇到b重复，i本来正常应该是保存为1，但是重复字符
            //c的位置靠后，所以i仍然为2（因为你保存1没有用，中间还是存在c重复）
            if (index[s.charAt(j)] > i) {
                i = index[s.charAt(j)] + 1;
            }
            maxLen = Math.max(maxLen, j - i + 1);
            //把字符和字符对应的下标位置存起来，用于i进行跳转
            index[s.charAt(j)] = j;
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(solution_3("rewfdaadsfghjrtyueertgdfgd"));
    }
}
